As computing power increases, scientists and engineers increasingly rely on a computer's abilities to perform operations on large sets of physical or statistical data. In other cases, large sets of data are created at an internal state of the execution of a computer program and must be operated on for the program to continue. Oftentimes, these data sets are maintained in the form of matrices. A frequent task of a programmer working on a program to manipulate large matrices is to minimize the time taken when multiplying these matrices to produce a third, or product matrix.
Traditionally, the process of multiplying two matrices of size n×n would take 2n3 steps to complete. For many applications, the fact that the processing time grows with the cube of the size of the matrix means that computational times can become unwieldy. In order to improve performance, various alternative matrix-multiplication methods have been proposed, beginning with the work of Strassen in 1969 and continuing to the work of Coppersmith and Winograd in 1987. Each of these techniques has given methods of multiplying matrices which takes fewer than 2n3 steps. Unfortunately, the newer techniques have become increasingly specialized and difficult to implement. Additionally, there has been little improvement on these techniques in recent years, reaching a best bound for matrix multiplication of O(n2.38) steps, meaning the number of steps is bounded by a constant times n2.38. Current methods have thus reached a point of stagnation with respect to performance improvements.
What is needed is a framework for techniques of efficient multiplication of large matrices which provides results in fewer than 2n3 steps.